1. Field of the Invention
The present invention relates to a method of and an apparatus for designing a circuit block layout in an integrated circuit, and more specifically to a method and an apparatus that are preferable for designing a floor plan in an SOG (Sea of Gate) and a macro cell layout as well as for designing a circuit block layout in a PLD (Programmable Logic Device) by use of a CAD (Computer Aided Design) apparatus, and further that are capable of designing in a short time the layout of circuit blocks such that they have a minimum total wiring length.
2. Description of the Prior Art
There is known an SOG as a large scale integrated circuit (LSI) being capable of laying out and wiring macro cells in an arbitrary region in a chip and having high flexibility on a design. For determination of such laying-out and wiring of each macro cell, it is necessary to lay out macro cells of given sizes and shapes in frames of a die having predetermined size of about four kinds (die size or chip size) for example such that the wiring distance between adjacent macro cells is minimized. In order to reduce the delay time of signal transmission and a wiring area, it is desirable to minimize the wiring distance between adjacent macro cells, and for SOGs having the same function it is desirable to also reduce the die size or chip size to the utmost.
For this purpose, there is known a hierarchical design method in which an integrated circuit is divided into functional areas in the unit of a large macro cell and wired without arranging small transistors in the circuit from the first, and then those small transistors are placed in each functional group and wired.
Also in the hierarchical design method, however, it is necessary to lay out macro cells each having a predetermined size and shape in a chip of a given size so as to minimize the wiring length between adjacent macro cells. This is a kind of problem of cutting small plates out of a large plate and there are infinite number of combinations of layouts. Prior practice to adjust the layout and shape of each macro cell therefore uses a dialogue graphic screen of a development tool for a CAD apparatus to perform the adjustment manually in trial and error, requiring time-consuming work.
For such a development tool, there is known for example an LSI layout designing device according to the hierarchy layout system disclosed for example in Japanese Laid-Open Patent Publication No. 63-181348, the device comprising a layout specification memory section, rough layout determining means, a rough layout information memory section, block layout determining means, a block layout information memory section, chip layout determining means, chip layout information memory section, and mask pattern synthesizing means.
Additionally, for designing the layout of a very large scale integrated circuit (VLSI) according to the hierarchy designing system, there is proposed a technique disclosed in for example "Data in the Meeting for the Research of the Design Automation in the society of Information Transaction, 18-3, September 1983", in which a chip floor plan is semiautomatically performed of the layout of a circuit block level, a first stage of the layout. In this technique, an initial layout of a circuit block is performed by an attractive and repulsive force method (AR method) with use of a spring model of a mass point system where the circuit blocks of an infinitesimal size are coupled through springs. In succession block packing processing is applied to the initial layout in which circuit blocks are provided with rectangles to correspond to an actual shape and the circuit blocks are moved manually in trial and error to eliminate any overlapping between adjacent circuit blocks, and the circuit blocks separated from each other are brought into close contact. In the latter half of the processing, aspect ratios of variable-shape circuit blocks are also altered manually to eliminate any overlapping among the circuit blocks. Additionally, there are calculated regions required for wirings among the circuit blocks on the basis of wiring information among the circuit blocks and of positional information of those circuit blocks.
Alternatively, there is proposed a circuit block layout technique in the Journal of the Society of Electronic Information Communication 89/I, Vol. J 72-A, No. 1, in which there is adopted a force directed method in which there are exerted on the circuit blocks attractive force corresponding to the number of wirings and repulsive force corresponding to the area of overlapping. In the circuit block layout technique, the circuit blocks 1 through 17 are rendered to the initial layout in a frame of a die 20 only with the aid of the attractive force by the wirings so as to minimize the square-sum of wiring lengths, as illustrated in FIG. 37. In succession, for the initial layout the repulsive force is gradually increased with an initial value 1/100 times the attractive force and the overlapping is gradually removed by repeated calculation such that the ratio of an overlapping area to the total area of the circuit blocks is 8.2% or less. Hereby, a relative positional relation among the circuit blocks 1 to 17 is substantially defined, as illustrated in FIG. 38. Further, orientations of the circuit blocks are examined in succession from those located distantly from the center of the layout region 20, as illustrated in FIG. 39. Finally, balanced positions of the circuit blocks are defined and the orientations of the circuit blocks are rechecked to determine the layout of the blocks, as illustrated in FIG. 40.
Herein, in the foregoing technique, slight overlapping is left behind corresponding to a fraction to balance the attractive force by the wirings. There is therefore proposed a modified technique to establish a layout without overlapping, as illustrated in FIG. 41, by expanding the circuit blocks by a slight length prior to the layout, gradually eliminating any overlapping existent among the circuit blocks until a maximum overlapping length among the circuit blocks is less than the amount of the expansion, and further returning those circuit blocks to original sizes.
In the aforementioned techniques, however, all circuit blocks are processed as rectangles and hence are not easy in movement thereof. Additionally, in the latter technique, each circuit block is not adjusted in its aspect ratio (vertical to lateral length ratio). Accordingly, there are occasions where a compact layout is not necessarily achieved as a whole provided particularly use is made of variable-shape circuit blocks such as soft macros that are variable in their aspect ratios. Further, in the aforementioned techniques circuit block positions are moved in the die frame 20 to eliminate any overlapping among the circuit blocks which was produced in the initial layout. Accordingly, the circuit block positions may sometimes be moved in excess during a process of determination of the layout, resulting in difficulties that there might be lost the conditions of the total wiring length and any dead space being both minimum.
Further, there is known a programmable logic device (PLD) for example as an integrated circuit (IC) for which a user is free to program internal wirings thereof for realization of a desired logic operation thereof.
Such a PLD is a writable and rewritable high integrated circuit including a plurality of various logic elements, say, having such a structure, as illustrated in FIG. 42, that there are previously disposed regularly in the form of a lattice programmable logic elements (PLEs) 22 as circuit blocks each with input/output pins 21 and switching stations (SSs) including switching elements (MOSFETs, for example).
In order for a user to realize a desired logic using such a PLD, a specific switching element in a specific SS is switched on to determine proper wiring direction in the SS, and wiring paths are formed among input/output pins of PLEs that are necessary for realization of the desired logic.
For this purpose, a circuit block layout design is necessary on how those PLEs are laid out in the PLD and on how the wiring paths are formed among those PLEs through the SSs.
Now, the total wiring length in the PLD should be made minimum in order to reduce the delay time of signal transmission in the PLD. It is therefore necessary to previously design the layout of the PLEs such that the total wiring length is minimum.
Prior practices to realize such a requirement are known which is capable of automatically designing the layout of the PLEs.
One example is disclosed as a simulated annealing method in Nikkei Electronics, Jul. 28, 1986 (No. 400), P 289 and thereafter.
In the simulated annealing method, a circuit block layout design is achieved such that it is judged by the following equation whether or not pair exchange among circuit blocks should be done, and the pair exchange is continued according to the result of the judgement so as to shorten the total wiring length: EQU exp [-(E.sub.2 -E.sub.1)/T].gtoreq.R (1)
where E.sub.1 and E.sub.2 are estimating functions respectively before and after the exchange, T is a parameter from 0 to .infin., and R is a uniformly generated random number from 0 to 1. If the equation (1) holds, the circuit blocks undergo the pair exchange, and if not so, it does not undergo such exchange.
In the simulated annealing method, however, it is judged for each circuit block on the basis of the foregoing equation whether or not the circuit blocks should undergo the pair exchange, so that there is required long time for a design until a final layout of the circuit blocks is determined. For example, a PLD with 36 circuit blocks, 4.6 hours are required for determining the layout.
Additionally, for the layout design of the PLD which has strongly coupled PLEs, it is preferable in view of the reduction of the wiring length and of the prevention of any time delay to construct macro circuit blocks of various different sizes by directly connecting the PLEs through exclusive lines without mediating the SSs. However, in the aforementioned simulated annealing method, the block layout is optimized through the pair exchange of circuit blocks each with the same or substantially the same size, e.g., rectangular ones each having different lengths only longitudinally or laterally. It is therefore difficult to automatically optimize the layout of circuit blocks of different sizes, e.g., rectangular circuit blocks of different longitudinal and lateral lengths. Furthermore, if the layout of macro circuit blocks of various sizes is performed manually in trial and error observing a dialogic graphics screen of a CAD device to reduce the wiring length, it requires much time for the design, and if the design is performed manually in trial and error, the requirement to minimize the wiring length might be lost.